package Test_1130;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Sort {
    //时间复杂度：
    //空间复杂度
    //直接插入排序
    public static void insetSort(int[] array){
        //为什么i=1；
        for (int i = 1; i < array.length ; i++) {
            int tmp=array[i];
            int j=i-1;
            for (; j >=0 ; j--) {
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{
                    array[j+1]=tmp;
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }
//希尔排序：缩小增量排序
    //不稳定
    //时间复杂度：n^1.25-n^1.3
    //空间复杂度：O（1）
    public static void shellSort(int[] array) {

    }
    public static void shell(int[] array,int gap){
        //为什么i=1；
        for (int i = gap; i < array.length ; i++) {
            int tmp=array[i];
            int j=i-gap;
            for (; j >=0 ; j--) {
                if(array[j]>tmp){
                    array[j+gap]=array[j];
                }else{
                    array[j+gap]=tmp;
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }
    public static void selectSort1(int[] array){
        for (int i = 0; i < array.length; i++) {
            int mindIndex=i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j]<array[mindIndex]){
                    mindIndex=j;
                }
            }
            swap(array,i,mindIndex);
        }
    }
    //有问题
    public static void selectSort(int[] array){
        int left=0;
        int right= array.length-1;
        while(left<right){
            int minIndex=left;
            int maxIndex=left;
            for (int i = left+1; i <= right; i++) {
                if(array[i]<minIndex){
                    minIndex=i;
                }
                if(array[i]>maxIndex){
                    maxIndex=i;
                }
                swap(array,left,minIndex);
                //最大值正好是left，此时把最大值换成minIndex
                if(maxIndex==left){
                    maxIndex=minIndex;
                }
                swap(array,right,maxIndex);
                left++;
                right--;
            }

        }    }
    
    private static void swap(int[] array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }}
